/* 最长单调递增子序列 */
#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std;

int main(void)
{
	constexpr int N = 8;
	int a[N] = {1, 3, 5, 2, 4, 6, 7, 8};

	int ans[N]{0};
	int len{0};
	vector<int> vLIS[N];

	ans[0] = a[0];
	len = 1;
	vLIS[0].push_back(a[0]);

	for (int i = 1; i < N; i++)
	{
		int temp = a[i];

		if (temp > ans[len - 1])
		{
			ans[len] = temp;
			vLIS[len].assign(vLIS[len - 1].begin(), vLIS[len - 1].end());
			vLIS[len].push_back(temp);
			len++;
		}
		else
		{
			int *p = lower_bound(ans, ans + len, temp);
			int idx = p - ans;
			vLIS[idx].pop_back();
			*p = temp;
			vLIS[idx].push_back(temp);
		}
	}

	cout<< "the length of longest increasing string is: " << len;
	cout<< ", and the LIS is: ";
	copy(vLIS[len - 1].begin(), vLIS[len - 1].end(), ostream_iterator<int>(cout, " "));
	cout<< endl;

	return 0;
}
